//设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。 
//
// 示例： 
//
// 输入： arr = [1,3,5,7,2,4,6,8], k = 4
//输出： [1,2,3,4]
// 
//
// 提示： 
//
// 
// 0 <= len(arr) <= 100000 
// 0 <= k <= min(100000, len(arr)) 
// 
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 248 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2025-09-16 23:01:08
 * @description 面试题 17.14.最小K个数
 */
public class SmallestKLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SmallestKLcci fun=new SmallestKLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 原有的PQ
    public int[] smallestK1(int[] arr, int k) {
		PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
		for (int i : arr) {
			priorityQueue.offer(i);
		}
		int [] res=new int[k];
		for (int i = 0; i < k; i++) {
			res[i]=priorityQueue.poll();
		}
		return res;
    }
	// 快速选择算法是快速排序的变种，可以在平均O(n)的时间内找到第k小的元素，然后返回前k个元素。
	public int[] smallestK2(int[] arr, int k) {
		if (k == 0) return new int[0];
		quickSelect(arr, 0, arr.length - 1, k - 1);
		return Arrays.copyOf(arr, k);
	}

	private void quickSelect(int[] arr, int left, int right, int k) {
		if (left >= right) return;

		int pivot = partition(arr, left, right);
		if (pivot == k) {
			return;
		} else if (pivot < k) {
			// 如果pivot小于k，说明k在右侧，缩小左侧边界
			quickSelect(arr, pivot + 1, right, k);
		} else {
			// 如果pivot大于k，说明k在左侧，缩小右侧边界
			quickSelect(arr, left, pivot - 1, k);
		}
	}

	private int partition(int[] arr, int left, int right) {
		int pivot = left;
		int index = pivot + 1;
		for (int i = index; i <= right; i++) {
			if (arr[i] < arr[pivot]) {
				swap(arr, i, index);
				index++;
			}
		}
		swap(arr, pivot, index - 1);
		return index - 1;
	}
	private int partition1(int[] arr, int left, int right) {
		// 选择中间元素作为pivot（避免最坏情况）
		int mid = left + (right - left) / 2;
		swap(arr, mid, right);
		int pivot = arr[right];

		int i = left;
		for (int j = left; j < right; j++) {
			if (arr[j] <= pivot) {
				swap(arr, i, j);
				i++;
			}
		}
		swap(arr, i, right);
		return i;
	}

	private void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	public int[] smallestK3(int[] arr, int k) {
		if (k == 0) return new int[0];

		// 构建最小堆
		buildMinHeap(arr);

		int[] result = new int[k];
		int heapSize = arr.length;

		// 提取前k个最小元素
		for (int i = 0; i < k; i++) {
			result[i] = arr[0]; // 堆顶是最小元素
			// 将最后一个元素移到堆顶，然后调整堆
			arr[0] = arr[heapSize - 1];
			heapSize--;
			minHeapify(arr, 0, heapSize);
		}

		return result;
	}

	// 构建最小堆
	private void buildMinHeap(int[] arr) {
		int n = arr.length;
		for (int i = n / 2 - 1; i >= 0; i--) {
			minHeapify(arr, i, n);
		}
	}

	// 最小堆调整
	private void minHeapify(int[] arr, int i, int heapSize) {
		int smallest = i;
		int left = 2 * i + 1;
		int right = 2 * i + 2;

		if (left < heapSize && arr[left] < arr[smallest]) {
			smallest = left;
		}

		if (right < heapSize && arr[right] < arr[smallest]) {
			smallest = right;
		}

		if (smallest != i) {
			swap(arr, i, smallest);
			minHeapify(arr, smallest, heapSize);
		}
	}
	//最大堆方法：时间复杂度 O(n log k)，空间复杂度 O(k)
	//最小堆方法：时间复杂度 O(n + k log n)，空间复杂度 O(n)
	public int[] smallestK4(int[] arr, int k) {
		if (k == 0) return new int[0];
		if (k >= arr.length) return arr.clone();

		// 使用最大堆来维护最小的k个数
		int[] maxHeap = new int[k];

		// 初始化最大堆
		for (int i = 0; i < k; i++) {
			maxHeap[i] = arr[i];
		}
		buildMaxHeap(maxHeap);

		// 处理剩余元素
		for (int i = k; i < arr.length; i++) {
			if (arr[i] < maxHeap[0]) {
				maxHeap[0] = arr[i];
				maxHeapify(maxHeap, 0, k);
			}
		}

		return maxHeap;
	}

	// 构建最大堆
	private void buildMaxHeap(int[] arr) {
		int n = arr.length;
		for (int i = n / 2 - 1; i >= 0; i--) {
			maxHeapify(arr, i, n);
		}
	}

	// 最大堆调整
	private void maxHeapify(int[] arr, int i, int heapSize) {
		int largest = i;
		int left = 2 * i + 1;
		int right = 2 * i + 2;

		if (left < heapSize && arr[left] > arr[largest]) {
			largest = left;
		}

		if (right < heapSize && arr[right] > arr[largest]) {
			largest = right;
		}

		if (largest != i) {
			swap(arr, i, largest);
			maxHeapify(arr, largest, heapSize);
		}
	}
	//基于归并排序思想的分治
	public int[] smallestK5(int[] arr, int k) {
		if (k == 0) return new int[0];
		if (k >= arr.length) return arr.clone();

		int[] result = new int[k];
		// 使用分治找到前k个最小元素
		divideAndConquer(arr, 0, arr.length - 1, k, result, 0);
		return result;
	}

	private void divideAndConquer(int[] arr, int left, int right, int k, int[] result, int resultIndex) {
		if (k <= 0 || left > right) return;

		if (right - left + 1 <= k) {
			// 如果当前子数组元素数量 <= k，直接全部加入结果
			for (int i = left; i <= right && resultIndex < result.length; i++) {
				result[resultIndex++] = arr[i];
			}
			return;
		}

		// 分治：分区操作
		int pivotIndex = partition(arr, left, right);
		int leftCount = pivotIndex - left;

		if (leftCount >= k) {
			// 左半部分已经有足够的元素
			divideAndConquer(arr, left, pivotIndex - 1, k, result, resultIndex);
		} else {
			// 左半部分全部加入结果，继续在右半部分找剩余的元素
			for (int i = left; i < pivotIndex && resultIndex < result.length; i++) {
				result[resultIndex++] = arr[i];
			}
			// 加入pivot元素
			if (resultIndex < result.length) {
				result[resultIndex++] = arr[pivotIndex];
			}
			// 在右半部分继续找剩余的元素
			divideAndConquer(arr, pivotIndex + 1, right, k - leftCount - 1, result, resultIndex);
		}
	}
	//三路分治（更稳定的版本）
	public int[] smallestK(int[] arr, int k) {
		if (k == 0) return new int[0];
		if (k >= arr.length) return arr.clone();

		threeWayQuickSelect(arr, 0, arr.length - 1, k);
		return Arrays.copyOf(arr, k);
	}

	private void threeWayQuickSelect(int[] arr, int left, int right, int k) {
		if (left >= right) return;

		// 三路分区：将数组分为 < pivot, = pivot, > pivot 三部分
		int[] bounds = threeWayPartition(arr, left, right);
		int lt = bounds[0]; // 小于pivot的结束位置
		int gt = bounds[1]; // 大于pivot的开始位置

		if (k <= lt - left) {
			// 前k个元素都在小于pivot的部分
			threeWayQuickSelect(arr, left, lt - 1, k);
		} else if (k > gt - left) {
			// 需要在大于pivot的部分继续找剩余元素
			threeWayQuickSelect(arr, gt, right, k - (gt - left));
		}
		// 否则，前k个元素已经包含所有小于pivot和部分等于pivot的元素，直接返回
	}

	private int[] threeWayPartition(int[] arr, int left, int right) {
		// 选择随机pivot避免最坏情况
		int randomIndex = left + (int)(Math.random() * (right - left + 1));
		swap(arr, randomIndex, right);
		int pivot = arr[right];

		int lt = left;      // 小于pivot的边界
		int gt = right;     // 大于pivot的边界
		int i = left;

		while (i <= gt) {
			if (arr[i] < pivot) {
				swap(arr, lt++, i++);
			} else if (arr[i] > pivot) {
				swap(arr, i, gt--);
			} else {
				i++;
			}
		}

		return new int[]{lt, gt + 1};
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
